The present invention relates to a method for testing the primality of numbers. In particular, the present invention relates to a method that deterministically tests whether a given number is prime, in polynomial time. This invention has particular applicability to “public key” and other encryption techniques that play an important role in the security of information technology and electronic commerce.
Prime numbers are positive integers divisible only by themselves and 1. Prime numbers are unique building blocks of all positive integers. Every positive integer greater than one can be expressed uniquely as a product of primes, apart from rearrangement of terms.
Prime numbers have been of interest to mathematicians since ancient times. There have been continuous attempts to identify new prime numbers. Though it is easy to test the primality of small numbers, the problem becomes complex as the number becomes large. Identifying new prime numbers and testing the primality of any given number have been important and challenging mathematical problems.
One of the earliest methods of testing primality is the Sieve of Eratosthenes. This method tests the primality of an integer ‘n’ by trying to divide the integer ‘n’ with all prime numbers less than or equal to the square root of ‘n’. This method thus involves finding all prime numbers that are less than or equal to the square root of ‘n’. Though the Sieve of Eratosthenes provides a deterministic method for testing primality, the time involved in testing increases exponentially with respect to the number of digits (in a given integer).
In seventeenth century, Fermat proved that for any prime number ‘p’, and any number ‘a’ not divisible by p, the following equation holds:ap−1=1 mod(p)
This is known as Fermat's Little Theorem and has been the basis of several primality testing algorithms.
The methods of testing primality have gained further importance with increasing use of encryption in electronic communication. Prime numbers form the basis of most encryption techniques and therefore play an important role in security and cryptography in Information Technology.
Public-key encryption methods such as El Gamal encryption, Elliptic-curve public-key encryption, Diffie-Hellman key exchange and RSA utilize prime numbers. Public-key cryptography is one of the standard forms of encryption for electronic correspondence. The security arising in this type of cryptography primarily relies on the difficulty involved either in factoring very large numbers or computing a discrete logarithm modulo of a large prime.
Various encryption methods such as those given above require large prime numbers in order to produce cryptographic keys, which are used to encipher and decipher data. The larger the prime number (used for generating the encryption key), the more difficult it is to obtain the decryption key from the encryption key and the more secure is the encryption. Thus, generating large prime numbers is one of the key problems associated with cryptography.
Prime numbers involved in encryption are usually very, very large. Testing the primality of such large numbers is a complex task. By way of an example, if the Sieve of Eratosthenes were used to determine the primality of a number with just 20 digits, then it would require one to first find at least all prime numbers up to 1010. It is believed that there are around 450 million primes less that 1010. Assuming a rate of finding one prime per second (including elimination of all of its multiples), the time required to find 450 million primes would be around 14 years! These prime numbers will in-turn have to be tested whether they divide the original 20-digit number, to test the primality.
Though the above example provides a deterministic method of testing primality, it has an exponential time complexity, that is, the time taken to come to the decision of primality is bounded by an exponential function, which is dependent on the size of the input number. This limits its use in present day systems for testing primality of large numbers.
Several methods have been developed for the purpose of generating and testing large prime numbers. These methods are either deterministic or randomized. In deterministic methods, the number is declared to be prime or composite with no probability of error.
Since deterministic algorithms take exponential computational time, researchers have tried to develop randomized methods to solve the primality problem. Randomized methods for primality testing are faster than current deterministic methods. However, such methods have an associated probability of error. The probability of errors associated with such methods is inversely proportional to the time required for executing these methods. That is, if the probability of error of such methods were reduced, then the time complexity would increase. Randomized algorithms like Miller-Rabin algorithm may be suitable for many applications, but for sensitive applications like financial transactions and national security, an error-proof method is usually preferable.
There exist patents that have been filed and granted for generating prime numbers and testing the primality of a number. U.S. Pat. No. 6,307,938 entitled “Method, System And Apparatus For Generating Self-Validating Prime Numbers”, assigned to International Business Machines Corporation (Armonk, N.Y., USA), and filed on Jul. 10, 1998, describes one such method for generating prime numbers for use in cryptography. This method provides an encoding method that permits secret seed values to be encoded into the generated prime numbers. The method generates suitable seed numbers, which are then used for generating prime numbers using standard methods.
U.S. patent application Ser. No. 20030108193, entitled “Key Generation Performance Improvement”, assigned to Howard Hughes Center (CA, USA), and filed on Oct. 29, 2002, describes a method and apparatus for generation of large prime numbers for use in a cryptographic system. The method described in this patent application uses a “mod remainder” based approach for generating prime numbers in conjunction with standard primality testing methods like Fermat's Little Theorem. For a prime number, the mod remainders cannot be zero. This method creates and maintains a table of mod remainders (for all primes less than a defined range) for a number. If all the mod remainders in the table are non-zero, then the number is further tested for primality by standard primality testing methods.
Most of the above-mentioned methods either have a high time complexity, or there is a small chance of the answer being incorrect. In other words, either the methods are probabilistic or are super-polynomial in time, that is, the time taken to come to the decision of primality cannot be bounded by any polynomial function.
Accordingly, what is required is a method for testing primality that has polynomial time complexity and is also deterministic. The term polynomial time means that the time taken to come to the decision of primality is bounded by a polynomial, which is dependent on the size of the input number.